package 回溯;


import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode.cn/problems/permutations/?favorite=2cktkvj
 *
 * 题解：https://leetcode.cn/problems/permutations/?favorite=2cktkvj
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,2,3]
 * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 * 示例 2：
 *
 * 输入：nums = [0,1]
 * 输出：[[0,1],[1,0]]
 * 示例 3：
 *
 * 输入：nums = [1]
 * 输出：[[1]]
 */
public class _46_全排列 {

    List<List<Integer>> resultList;
    List<Integer> result;

    int[] nums;

    public List<List<Integer>> permute(int[] nums) {
        this.result = new ArrayList<>();
        this.resultList = new ArrayList<>();
        this.nums = nums;
        dfs();
        return resultList;
    }

    private void dfs() {

        if (result.size() == nums.length) {
            List<Integer> res = new ArrayList<>();
            for (int i = 0; i < result.size(); i++) {
                res.add(result.get(i));
            }

            resultList.add(res);
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (result.contains(nums[i])) {
                continue;
            }
            result.add(nums[i]);
            dfs();
            result.remove(result.size() - 1);
        }
    }
}
